#include <intersectionConvexPolygons.h>
#include <szMiscOperations.h>

namespace _IntersectConvexPolygon
{
	struct structLine
	{
		structLine()
		{
			ref = CParticleF();
			angle = 0.0f;
			bValid = false;
		}
		structLine(CParticleF& ref, float a)
		{
			this->ref = ref;
			angle = a;
			bValid = true;
		}
		CParticleF ref;
		float angle;
		bool bValid;
	};

	CParticleF
	mostLeft(std::vector<CParticleF>& points)
	{
		CParticleF left = points[0];
		for(int i=1; i<points.size(); ++i)
		{
			if(points[i].m_X < left.m_X)
			{
				left = points[i];
			}
		}
		return left;
	}

	/*
	This implement an algorithm by Godfried Toussaint to find the intersection of two convex polygons.
	See http://www.iro.umontreal.ca/~plante/compGeom/algorithm.html for more.
	*/
	std::vector<CParticleF> 
	intersectConvexHulls(std::vector<CParticleF>& P, 
						 std::vector<CParticleF>& Q)
	{
		std::vector<CParticleF> cap;

		//find the most left one 
		CParticleF p = mostLeft(P);
		CParticleF q = mostLeft(Q);

		structLine lineP(p, PI/2.0);
		structLine lineQ(q, PI/2.0);
		structLine lid[2];
		int relativePos;
		//find two pocket lids
		while(lid[0].bValid==false && lid[1].bValid==false)
		{

		}
		return cap;
	}
}
